package com.dataStructure.并查集;

/**
 * 路径分裂（Path Spliting）：实现成本比路径压缩低
 * 路径分裂、路径减半的效率差不多，但都比路径压缩要好
 *
 * 路径分裂：使路径上的每个节点都指向其祖父节点（parent的parent）
 *      即 Quick Union - 基于rank的优化 - 路径分裂
 */

@SuppressWarnings("all")
public class 并查集_QuickUnion_路径分裂优化 extends 并查集_QuickUnion_Rank优化{

    public 并查集_QuickUnion_路径分裂优化(int capacity) {
        super(capacity);
    }

    @Override
    public int find(int v) {
        rangCheck(v);

        while (v != parents[v]){
            //保留一下v的父节点，避免v指向其祖父节点的同时，丢失到其父节点
            int p = parents[v];
            //将v节点指向其祖父节点
            parents[v] = parents[parents[v]];
            //v的父节点p变成v，重复指向祖父节点的操作
            v = p;
        }
        return v;
    }
}
